Tổ tiên ba anh em Tây Sơn ở làng Hương Cái, huyện Hưng Nguyên, tỉnh Nghệ An. Họ theo chúa Nguyễn vào lập nghiệp miền Nam khi chúa Nguyễn vượt Lũy Thầy đánh ra đất Lê – Trịnh tới Nghệ An vào niên hiệu Thịnh Đức (1653–1657) đời Lê Thần Tông. Ông cố của "Tây Sơn tam kiệt" tên là Hồ Phi Long, vào giúp việc cho nhà họ Đinh ở thôn Bằng Chân, huyện Tuy Viễn (tức An Nhơn), cưới vợ họ Đinh và sinh được một trai tên là Hồ Phi Tiễn. Hồ Phi Tiễn không theo việc nông mà bỏ đi buôn trầu ở ấp Tây Sơn, cưới vợ và định cư tại đó. Bà vợ tên là Nguyễn Thị Đồng, con gái duy nhất của một phú thương đất Phú Lạc, do đó nên họ đổi con cái từ họ Hồ sang họ Nguyễn của mẹ. Vì vậy, người con có tên là Nguyễn Phi Phúc. Nguyễn Phi Phúc cũng chuyên nghề buôn trầu và trở nên mỗi ngày mỗi giàu có (cũng có tài liệu cho rằng họ Hồ đã đổi theo họ chúa Nguyễn ngay từ khi mới vào Nam).

Nguyễn Phi Phúc có tám người con, trong đó có ba người con trai: Nguyễn Nhạc, Nguyễn Lữ và Nguyễn Huệ. Các tài liệu không hoàn toàn thống nhất về thứ tự của ba người con này, chỉ biết Nguyễn Nhạc là anh cả, còn Nguyễn Huệ và Nguyễn Lữ không rõ ai lớn hơn ai. Có tài liệu nói Nguyễn Lữ là người con thứ 3 và là con trai út (thầy Tư Lữ), có tài liệu cho ông là người con trai thứ 6 (Đức ông Bảy). Trong ba anh em, Nguyễn Lữ là người thiếu mạnh mẽ hơn cả. Ông được đánh giá là người nhân hậu, khoan hoà.

Nguyễn Lữ còn gọi là Nguyễn Văn Lữ theo tên gọi trong sử, sinh năm Giáp Tuất (1754), tại làng Kiên Mỹ, huyện Tuy Viễn. Là em thứ ba sau Nguyễn Nhạc, Nguyễn Huệ. Lớn lên theo hai anh xuống Bàng Châu thụ giáo Đinh Công hai năm rồi lên An Thái, theo học văn lẫn võ cùng thầy Trương Văn Hiến.

Nguyễn Lữ đã được thầy là Trương Văn Hiến chân truyền cho môn miên quyền. Môn này cũng là món sở trường của Trương Công. Vốn người mảnh khảnh, tính nết hiền hòa, ưa thanh tịnh. Khác với hai anh, ông học văn nhiều hơn học võ. Tuy nhiên, ông cũng đã học hết các môn võ và chuyên về môn miên quyền. Môn miên quyền còn gọi là nhu quyền, là một môn võ nghệ chuyên dùng sức nhẹ để thắng mạnh, hợp với phụ nữ và những người thích võ nhưng tính ôn hòa. Phần đông đều dùng nhu quyền để tự vệ hơn tấn công. Ngoài ra, Nguyễn Lữ cũng chuyên về kiếm, nhờ ở sự phối hợp giữa miên quyền và kiếm thuật, ông Lữ đã nổi danh về môn nhu kiếm. Kiếm của ông nhẹ và mỏng nhưng lại sắc bén vô cùng nhờ ở biết thế nương vào sức mạnh của địch mà đánh trả, nên tuy kiếm mảnh mà không đao búa nào đánh gãy được.

Về văn học, ông lại ham thích nghiên cứu về tôn giáo, cho nên khi cha là Nguyễn Phi Phúc qua đời, Nguyễn Nhạc về nối nghiệp cha thì Nguyễn Lữ cũng thôi học, xuất gia theo Minh giáo, tục gọi là đạo Ma Ní, dùng phù phép để chữa bệnh, trừ tà như đạo phù thủy. Đạo minh giáo thờ thần lửa gần giống với sự thờ cúng của các dân tộc ít người tại Tây Sơn thượng. Đạo Ma Ní rất thịnh hành ở Tây Sơn thượng, nên Nguyễn Lữ qua việc truyền giáo đã quen biết rất nhiều các tộc trưởng, nhiều bộ lạc, người dân tộc thiểu số như sắc tộc Xà Đàn (Sédang), Ra Đê (Rhadé), Gia Rai (Djarais) v.v…

Nguyễn Lữ đi truyền đạo cũng như chữa bệnh cho mọi người khắp vùng Tây Sơn. Nhân dân thường gọi ông là Thầy Tư Lữ (có thuyết nói Nguyễn Văn Lữ là người sinh thứ ba trong gia đình, tục người Đàng Trong gọi người sinh đầu là anh hai để tướng nhớ nguồn gốc là dân Việt từ phía bắc di cư vào nam, Nguyễn Lữ sinh thứ ba nên gọi là Tư Lữ).

Trên đường hành đạo, Nguyễn Lữ nhờ đức tính hiền hòa cộng với sự tin tưởng vào bản thân tuyệt đối, hòa với võ công đặc biệt là môn miên quyền mà ông đã vượt qua mọi trở ngại, hiểm nguy. Khi gặp phải bọn côn đồ, không thể dùng lời lẽ ôn tồn khuyên răn, ông đã dùng đến vũ lực để chinh phục. Nhờ môn miên quyền mà ông đã thu phục được nhiều kẻ anh hùng, vũ dũng, sống ngoài vòng cương tỏa của xã hội, sau này trở thành tướng sĩ của nhà Tây Sơn.

Khi Nguyễn Nhạc dựng cờ khởi nghĩa, ông trở về cùng anh chung lo việc nước. Một phần lớn nhờ ở ông đi thuyết phục mà các sắc tộc miền Tây Sơn thượng theo về với nhà Tây Sơn. Việc thu phục được tộc trưởng Bốc Kiơm, ông đã dự vào một phần lớn. Khi Nguyễn Nhạc làm Tây Sơn Vương thì Nguyễn Lữ được giao trọng trách lo về kinh tế, tài chính, cùng với Nguyễn Thung và Bùi Thị Xuân.

Nguyễn Thung là một phú nông ở thôn Thuận Nghĩa, sát Kiên Mỹ, là một thôn trù phú. Nguyễn Thung tuy là một phú nông, song kinh sử đều thông thuộc. Tính tình hào phóng, nhân hậu. Trong nhà tân khách luôn luôn tấp nập. Biết võ nghệ, sở trường về môn trường tiên. Kết giao với nhiều tay anh hùng như ba anh em Tây Sơn, Võ Văn Dũng… là nhân vật đến với nhà Tây Sơn từ thuở ban đầu. Khi Tây Sơn khởi nghĩa, Nguyễn Thung đã đem tất cả tài sản ủng hộ nghĩa quân. Giữ nhiệm vụ vận tải, tiếp tế quân lương, ông được phong Tán Tương Quân vụ, lo ở mặt Bắc, còn Nguyễn Lữ lo mặt Nam.

Lúc tổng hành dinh dời lên Tây Sơn thượng, Nguyễn Lữ vẫn ở lại Tây Sơn hạ, tiếp tục đôn đốc sản xuất. Khi cần đến kế hoạch "thượng vận", ông mới lên cùng Nguyễn Nhạc ở Tây Sơn thượng. Ông là người có công đầu trong việc liên kết các sắc tộc với nhà Tây Sơn, vì ông vừa giỏi tiếng dân tộc vừa là nhà truyền giáo rất thích hợp với tôn giáo người miền Tây Sơn thượng. Trong việc chinh phục tộc trưởng Bốc Kiơm của tộc Xà Đàng Nguyễn Lữ là người tham mưu cho ông Nhạc, cũng như việc liên kết với tộc Ba na trong rừng Mộ Điểu. Để nâng cao uy danh Nguyễn Nhạc, Nguyễn Lữ dành mọi thực thi kế hoạch cho Nguyễn Nhạc. Kết quả các bộ tộc Tây Sơn thượng tôn Nguyễn Nhạc là vua trời (Thiên vương). Nguyễn Lữ đã cùng anh đi rộng lên Kontum, Pleiku. Đi đến đâu, thuyết phục người dân tộc đến đó và rất được đồng thanh liên kết. Trên bước đường đi liên minh cùng các sắc tộc vùng cao, Nguyễn Lữ cũng đã tuyên truyền cho đạo thần lửa của mình và tài nghệ dùng lá cây chữa bệnh đã giúp ông thu nhiều kết quả.

Ngày rằm tháng 8 năm Quý Tỵ (1773), Tây Sơn khởi nghĩa. Nguyễn Lữ được phong Tán Tương Quân vụ lo việc tiếp tế lương thực.

Sáng ngày 16, Nguyễn Lữ đã chuẩn bị sẵn sàng lương thực tại chân núi Đồng Phong, thôn Trinh Tường để đón tiếp đại quân xuất phát từ núi Bà Phù đêm hôm trước. Tại đây, tướng sĩ dừng chân, ăn uống no nê rồi đi thẳng một mạch xuống Tuy Viễn. Binh đi như gió cuốn. Mặt trời lên cao thì huyện lỵ đã bị bao vây. Tiếng quân hò reo vang trời. Tri huyện Tuy Viễn trốn chạy, binh sĩ trong huyện đầu hàng. Cho là nhờ ăn no, lãnh lương đầy đủ tại núi Đồng Phong, nên quân Tây Sơn chiến thắng dễ dàng. Do đó nhân dân gọi núi Đồng Phong là Hòn Lãnh Lương và gọi tắt là Hòn Lương.

Cuối thu năm ấy, sau khi chiếm được Quy Nhơn, đuổi chúa Nguyễn chạy vào Gia Định, Nguyễn Nhạc sai Nguyễn Lữ cùng Nguyễn Văn Lộc, Võ Văn Cao đi vào Phú Yên, Diên Khánh, Bình Thuận để xem xét tình hình và liên lạc với hai vua Thủy Xá (Potau Ea) và Hỏa Xá (Potau Apui) để liên minh và cổ động đồng bào địa phương hưởng ứng cuộc Nam chinh.